package pers.lls.hds.map;


/**
 * @author lilichai
 */
public class MstwGraph {
    private final int MAX_VERTS = 20;
    private final int INFINITY = 1000000;
    private MstwVertex MstwVertexList[];
    private int adjMat[][];
    private int nVerts;
    private int currentVert;
    private PriorityQ thePQ;
    private int nTree;

    public MstwGraph() {
        MstwVertexList = new MstwVertex[MAX_VERTS];

        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
        for (int j = 0; j < MAX_VERTS; j++)
            for (int k = 0; k < MAX_VERTS; k++)
                adjMat[j][k] = INFINITY;
        thePQ = new PriorityQ();
    }

    public void addMstwVertex(char lab) {
        MstwVertexList[nVerts++] = new MstwVertex(lab);
    }

    public void addEdge(int start, int end, int weight) {
        adjMat[start][end] = weight;
        adjMat[end][start] = weight;
    }

    public void displayMstwVertex(int v) {
        System.out.print(MstwVertexList[v].label);
    }

    public void mstw() {
        currentVert = 0;

        while (nTree < nVerts - 1) {
            MstwVertexList[currentVert].isInTree = true;
            nTree++;

            for (int j = 0; j < nVerts; j++) {
                if (j == currentVert)
                    continue;
                if (MstwVertexList[j].isInTree)
                    continue;
                int distance = adjMat[currentVert][j];
                if (distance == INFINITY)
                    continue;
                putInPQ(j, distance);
            }
            if (thePQ.size() == 0) {
                System.out.println(" MstwGraph NOT CONNECTED");
                return;
            }

            Edge theEdge = thePQ.removeMin();
            int sourceVert = theEdge.srcVert;
            currentVert = theEdge.destVert;

            System.out.print(MstwVertexList[sourceVert].label);
            System.out.print(MstwVertexList[currentVert].label);
            System.out.print(" ");
        }

        for (int j = 0; j < nVerts; j++)
            MstwVertexList[j].isInTree = false;
    }

    public void putInPQ(int newVert, int newDist) {

        int queueIndex = thePQ.find(newVert);
        if (queueIndex != -1) {
            Edge tempEdge = thePQ.peekN(queueIndex);
            int oldDist = tempEdge.distance;
            if (oldDist > newDist) {
                thePQ.removeN(queueIndex);
                Edge theEdge = new Edge(currentVert, newVert, newDist);
                thePQ.insert(theEdge);
            }

        } else {
            Edge theEdge = new Edge(currentVert, newVert, newDist);
            thePQ.insert(theEdge);
        }
    }

    public static void main(String[] args) {
        MstwGraph theMstwGraph = new MstwGraph();
        theMstwGraph.addMstwVertex('A');
        theMstwGraph.addMstwVertex('B');
        theMstwGraph.addMstwVertex('C');
        theMstwGraph.addMstwVertex('D');
        theMstwGraph.addMstwVertex('E');
        theMstwGraph.addMstwVertex('F');

        theMstwGraph.addEdge(0, 1, 6);
        theMstwGraph.addEdge(0, 3, 4);
        theMstwGraph.addEdge(1, 2, 10);
        theMstwGraph.addEdge(1, 3, 7);
        theMstwGraph.addEdge(1, 4, 7);
        theMstwGraph.addEdge(2, 3, 8);
        theMstwGraph.addEdge(2, 4, 5);
        theMstwGraph.addEdge(2, 5, 6);
        theMstwGraph.addEdge(3, 4, 12);
        theMstwGraph.addEdge(4, 5, 7);

        System.out.print("Minimum spanning tree: ");
        theMstwGraph.mstw();
        System.out.println();
    }

}

class Edge {
    public int srcVert;
    public int destVert;
    public int distance;

    public Edge(int sv, int dv, int d) {
        srcVert = sv;
        destVert = dv;
        distance = d;
    }

}

class PriorityQ {

    private final int SIZE = 20;
    private Edge[] queArray;
    private int size;

    public PriorityQ() {
        queArray = new Edge[SIZE];
        size = 0;
    }

    public void insert(Edge item) {
        int j;

        for (j = 0; j < size; j++)
            if (item.distance >= queArray[j].distance)
                break;

        for (int k = size - 1; k >= j; k--)
            queArray[k + 1] = queArray[k];

        queArray[j] = item;
        size++;
    }

    public Edge removeMin() {
        return queArray[--size];
    }

    public void removeN(int n) {
        for (int j = n; j < size - 1; j++)
            queArray[j] = queArray[j + 1];
        size--;
    }

    public Edge peekMin() {
        return queArray[size - 1];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return (size == 0);
    }

    public Edge peekN(int n) {
        return queArray[n];
    }

    public int find(int findDex) {
        for (int j = 0; j < size; j++)
            if (queArray[j].destVert == findDex)
                return j;
        return -1;
    }

}

class MstwVertex {
    public char label;
    public boolean isInTree;

    public MstwVertex(char lab) {
        label = lab;
        isInTree = false;
    }

}

